package com.kobeliu.entity;

/**
 * 出生的时候，差距是一条河流，我在这头，他在那头
 * 现在，差距是一个银河系，我在系外，他在系心
 * @Author: Kobe_Liu
 * @Date: 2021/12/6 10:20
 */

/**
 *给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 * 示例 1：
 *
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1
 *
 * 示例 2:
 *
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
 */

/**
 * 扯到数论了？
 * 我为什么要承受这些 尼玛的
 */
public class Demo_68_sword_14_1 {

    public static void main(String[] args) {

        int[] nums = new int[]{1,2,3,4,5,6,7};
        int sum = 1;
        for (int i = 1; i < nums.length; i++) {
            sum ^= nums[i];
        }
        System.out.println(sum);
    }


    /**
     * 数论
     *
     *     任何大于1的数都可由2和3相加组成（根据奇偶证明）
     *     因为2*2=1*4，2*3>1*5, 所以将数字拆成2和3，能得到的积最大
     *     因为2*2*2<3*3, 所以3越多积越大 时间复杂度O(n/3)，用幂函数可以达到O(log(n/3)),
     *     因为n不大，所以提升意义不大，我就没用。 空间复杂度常数复杂度O(1)
     *
     *     不会思想 抄的
     *     这里复杂度是 0(n/3)
     * @param n
     * @return
     */
    public static int cuttingRope1(int n) {
        //取最多的3？
        if(n<=3) return n-1;
        int sum = 1;
        while(n>3){
            if(n>6){
                sum *= 3;
                n -= 3;
            }
            if(n==6){
                sum *= 9;
                return sum;
            }
            if(n==5){
                sum *= 6;
                return sum;
            }
            if(n==4){
                sum *=4;
                return sum;
            }

        }
        return sum;
    }

    /**
     * 看不懂 算了算了
     * @param n
     * @return
     */
    public static int cuttingRope(int n) {
        if(n<=3) return n-1;

        int div = n/3;
        int rem = n % 3;
        long result = 1;
        for (int i = 0; i < div; i++) {
            result *= i<div-1 ? 3 : (rem == 2 ? 3*rem : (3+rem));
            if (result >= 1000000007) {
                result = result%1000000007;
            }
        }
        return (int)result;

    }

}
